package class13;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class PrintAllSubsquences3 {
    public static List<String> subs(String s){
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str,0,ans,path);
        return ans;
    }

    public static void process1(char[] str,int index,
                                List<String> ans,String path){
        if (index == str.length){
            ans.add(path);
            return;
        }
        process1(str,index+1,ans,path);
        process1(str,index+1,ans,path+String.valueOf(str[index]));
    }

    public static List<String> subsNoRepeat(String s){
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str,0,set,path);
        List<String> ans = new ArrayList<>();
        for (String cur : set){
            ans.add(cur);
        }
        return ans;
    }

    public static void process2(char[] str,int index,
                                HashSet<String> set,String path){
        if (index == str.length){
            set.add(path);
            return;
        }
        process2(str,index+1,set,path);
        process2(str,index+1,set,path + String.valueOf(str[index]));
    }

    public static void main(String[] args) {
        String test = "acccc";
        List<String> ans1 = subs(test);
        List<String> ans2 = subsNoRepeat(test);

        for (String cur : ans1){
            System.out.println(cur);
        }
        System.out.println("=========");
        for (String cur:ans2){
            System.out.println(cur);
        }
    }
}
